//在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 
//
// 
//
// 示例 1: 
//
// 输入: [7,5,6,4]
//输出: 5 
//
// 
//
// 限制： 
//
// 0 <= 数组长度 <= 50000 
// 👍 286 👎 0

package leetcode.editor.cn;
//Java：数组中的逆序对
public class ShuZuZhongDeNiXuDuiLcof{
    public static void main(String[] args) {
        Solution solution = new ShuZuZhongDeNiXuDuiLcof().new Solution();
        
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        public int reversePairs(int[] nums) {
            //归并排序
            if ( nums == null ){
                return 0;
            }
            int length = nums.length;
            if ( length < 2 ){
                return 0;
            }
            //不修改原来的数组
            int[] copyNums = new int[length];
            for (int i = 0; i < length; i++) {
                copyNums[i] = nums[i];
            }
            int[] temp = new int[length];
            return reversePairs( copyNums, 0, length-1, temp );
        }

        //归并排序，分
        private int reversePairs(int[] nums, int left, int right, int[] temp) {
            //递归终结者
            if ( left == right ){
                return 0;
            }
            int middle = left + (right-left) /2;
            //类似于后序遍历 LRN
            //左半部分
            int leftPairs = reversePairs( nums, left, middle, temp );
            //右半部分
            int rightPairs = reversePairs( nums, middle+1, right, temp );

            //已经是有序的了，提前剪枝，免得多余的操作
            if( nums[middle] <= nums[middle+1] ){
                return leftPairs + rightPairs;
            }
            //计算count 逆序和的数量
            int crossPairs = mergeAndCount( nums,left,middle,right,temp );
            return leftPairs + rightPairs + crossPairs;

        }
        //合并，在其中记录对应的逆序和数量
        private int mergeAndCount( int[] nums, int left, int middle, int right, int[] temp){
            for (int i = left;  i <= right ;  i++) {
                temp[i] = nums[i];
            }
            //左边的有序数组的左边界
            int leftNowBorder = left;
            //右边的有序数组的左边界
            int rightNowBorder = middle+1;
            int count = 0;
            for (int toBeSortedIndex = left; toBeSortedIndex <= right ; toBeSortedIndex++) {
                //此时左边的子数组长度为0
                if ( leftNowBorder == middle +1 ){
                    nums[toBeSortedIndex] = temp[rightNowBorder];
                    rightNowBorder++;
                }
                //此时右边的子数组长度为0
                else if( rightNowBorder == right+1 ){
                    nums[toBeSortedIndex] = temp[leftNowBorder];
                    leftNowBorder++;
                }
                //这儿必须得是“<=”，如是“<”，则归并排序是不稳定的
                //左边子数组的值较小，进入有序数组
                else if( temp[leftNowBorder] <= temp[rightNowBorder] ){
                    nums[toBeSortedIndex] = temp[leftNowBorder];
                    leftNowBorder++;
                }
                //此时，右边子数组的值较小，进入有序数组
                else {
                    nums[toBeSortedIndex] = temp[rightNowBorder];
                    rightNowBorder++;
                    count += ( middle - leftNowBorder +1);
                }
            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
